#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int gcd(int a, int b) {
    if (b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int is_prime(int n) {
    if (n <= 1)
        return 0;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0)
            return 0;
    }
    return 1;
}

int generate_prime() {
    int p;
    do {
        p = rand() % 100 + 1;
    } while (!is_prime(p));
    return p;
}

int mod_exp(int base, int exp, int mod) {
    int result = 1;
    while (exp > 0) {
        if (exp % 2 == 1)
            result = (result * base) % mod;
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

int main() {
    int p = generate_prime();
    int q = generate_prime();

    int n = p * q;
    int phi = (p - 1) * (q - 1);

    int e = 2;
    while (gcd(e, phi) != 1) {
        e++;
    }

    int d = 1;
    while ((d * e) % phi != 1) {
        d++;
    }

    printf("Public key: (%d, %d)\n", e, n);
    printf("Private key: (%d, %d)\n", d, n);

    int plaintext = 123;
    int ciphertext = mod_exp(plaintext, e, n);
    printf("Encrypted message: %d\n", ciphertext);

    int decrypted_text = mod_exp(ciphertext, d, n);
    printf("Decrypted message: %d\n", decrypted_text);

    return 0;
}
